/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW noweb 2.7 / examples / dag.nw

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 5c 73 65 63 74 69 6f 6e | 7b 43 6f 6e 76 65 72 74 |\section|{Convert|
|00000010| 69 6e 67 20 74 72 65 65 | 73 20 74 6f 20 64 61 67 |ing tree|s to dag|
|00000020| 73 7d 0d 54 68 65 20 70 | 72 6f 62 6c 65 6d 20 77 |s}.The p|roblem w|
|00000030| 69 74 68 20 74 68 65 20 | 74 72 65 65 73 20 67 65 |ith the |trees ge|
|00000040| 6e 65 72 61 74 65 64 20 | 69 6e 20 74 68 65 20 70 |nerated |in the p|
|00000050| 72 65 76 69 6f 75 73 20 | 73 65 63 74 69 6f 6e 20 |revious |section |
|00000060| 69 73 20 74 68 61 74 0d | 74 68 65 72 65 27 73 20 |is that.|there's |
|00000070| 61 20 64 69 66 66 65 72 | 65 6e 74 20 65 64 67 65 |a differ|ent edge|
|00000080| 2c 20 61 6e 64 20 74 68 | 65 72 65 66 6f 72 65 20 |, and th|erefore |
|00000090| 61 20 64 69 66 66 65 72 | 65 6e 74 20 63 68 69 6c |a differ|ent chil|
|000000a0| 64 2c 20 66 6f 72 20 65 | 61 63 68 0d 70 6f 73 73 |d, for e|ach.poss|
|000000b0| 69 62 6c 65 20 69 6e 74 | 65 72 76 61 6c 20 6f 66 |ible int|erval of|
|000000c0| 20 74 68 65 20 66 69 65 | 6c 64 20 74 65 73 74 65 | the fie|ld teste|
|000000d0| 64 2c 20 65 76 65 6e 20 | 69 66 20 74 68 6f 73 65 |d, even |if those|
|000000e0| 20 63 68 69 6c 64 72 65 | 6e 20 62 6f 74 68 0d 65 | childre|n both.e|
|000000f0| 78 65 63 75 74 65 20 65 | 78 61 63 74 6c 79 20 74 |xecute e|xactly t|
|00000100| 68 65 20 73 61 6d 65 20 | 60 60 6f 72 69 67 69 6e |he same |``origin|
|00000110| 61 6c 27 27 20 61 72 6d | 20 6f 66 20 74 68 65 20 |al'' arm| of the |
|00000120| 63 61 73 65 20 73 74 61 | 74 65 6d 65 6e 74 2e 0d |case sta|tement..|
|00000130| 54 68 65 20 63 6f 64 65 | 20 69 6e 20 74 68 69 73 |The code| in this|
|00000140| 20 73 65 63 74 69 6f 6e | 20 63 6f 6e 76 65 72 74 | section| convert|
|00000150| 73 20 74 68 65 20 74 72 | 65 65 73 20 74 6f 20 64 |s the tr|ees to d|
|00000160| 61 67 73 2c 20 61 6e 64 | 20 61 73 20 70 61 72 74 |ags, and| as part|
|00000170| 20 6f 66 0d 74 68 65 20 | 70 72 6f 63 65 73 73 20 | of.the |process |
|00000180| 69 74 20 63 6f 6d 62 69 | 6e 65 73 20 65 64 67 65 |it combi|nes edge|
|00000190| 73 20 70 6f 69 6e 74 69 | 6e 67 20 74 6f 20 74 68 |s pointi|ng to th|
|000001a0| 65 20 73 61 6d 65 20 6e | 6f 64 65 2e 0d 54 68 69 |e same n|ode..Thi|
|000001b0| 73 20 63 61 6e 20 72 65 | 64 75 63 65 20 74 68 65 |s can re|duce the|
|000001c0| 20 73 69 7a 65 20 6f 66 | 20 74 68 65 20 74 72 65 | size of| the tre|
|000001d0| 65 20 62 79 20 68 75 67 | 65 20 66 61 63 74 6f 72 |e by hug|e factor|
|000001e0| 73 2e 0d 0d 54 6f 20 6d | 61 6b 65 20 74 68 65 20 |s...To m|ake the |
|000001f0| 74 72 61 6e 73 66 6f 72 | 6d 61 74 69 6f 6e 20 77 |transfor|mation w|
|00000200| 6f 72 6b 2c 20 49 20 68 | 61 76 65 20 74 6f 20 72 |ork, I h|ave to r|
|00000210| 65 70 72 65 73 65 6e 74 | 20 61 20 7b 5c 65 6d 20 |epresent| a {\em |
|00000220| 73 65 74 20 6f 66 0d 69 | 6e 74 65 72 76 61 6c 73 |set of.i|ntervals|
|00000230| 7d 20 6f 6e 20 65 61 63 | 68 20 65 64 67 65 2c 20 |} on eac|h edge, |
|00000240| 6e 6f 74 20 6a 75 73 74 | 20 61 20 73 69 6e 67 6c |not just| a singl|
|00000250| 65 20 69 6e 74 65 72 76 | 61 6c 2e 20 20 42 65 63 |e interv|al.  Bec|
|00000260| 61 75 73 65 20 6e 6f 20 | 74 77 6f 20 69 6e 74 65 |ause no |two inte|
|00000270| 72 76 61 6c 73 0d 6f 76 | 65 72 6c 61 70 2c 20 49 |rvals.ov|erlap, I|
|00000280| 20 63 61 6e 20 75 73 65 | 20 61 20 77 6f 6e 64 65 | can use| a wonde|
|00000290| 72 66 75 6c 20 64 69 72 | 74 79 20 74 72 69 63 6b |rful dir|ty trick|
|000002a0| 2c 20 64 65 74 61 69 6c | 65 64 20 62 65 6c 6f 77 |, detail|ed below|
|000002b0| 2e 0d 49 20 61 6c 73 6f | 20 7b 5c 65 6d 20 6d 61 |..I also| {\em ma|
|000002c0| 79 7d 20 63 6f 6e 76 65 | 72 74 20 61 20 6e 6f 64 |y} conve|rt a nod|
|000002d0| 65 27 73 20 6e 61 6d 65 | 20 73 74 72 69 6e 67 20 |e's name| string |
|000002e0| 74 6f 20 61 20 5b 5b 6e | 61 6d 65 61 72 72 61 79 |to a [[n|amearray|
|000002f0| 5d 5d 20 6d 61 70 70 69 | 6e 67 0d 66 69 65 6c 64 |]] mappi|ng.field|
|00000300| 20 76 61 6c 75 65 73 20 | 74 6f 20 73 74 72 69 6e | values |to strin|
|00000310| 67 73 2e 20 20 54 68 65 | 20 67 6f 61 6c 20 69 73 |gs.  The| goal is|
|00000320| 20 66 6f 72 20 63 68 69 | 6c 64 72 65 6e 20 6f 66 | for chi|ldren of|
|00000330| 20 74 68 65 20 73 61 6d | 65 0d 70 61 72 65 6e 74 | the sam|e.parent|
|00000340| 20 74 6f 20 73 68 61 72 | 65 20 61 20 73 69 6e 67 | to shar|e a sing|
|00000350| 6c 65 20 6e 61 6d 65 20 | 61 72 72 61 79 3b 20 74 |le name |array; t|
|00000360| 68 61 74 20 77 61 79 20 | 74 68 65 20 65 64 67 65 |hat way |the edge|
|00000370| 73 20 63 61 6e 20 62 65 | 20 6d 65 72 67 65 64 20 |s can be| merged |
|00000380| 61 6e 64 0d 74 68 65 20 | 6e 61 6d 65 20 6f 70 65 |and.the |name ope|
|00000390| 72 61 74 6f 72 20 63 61 | 6e 20 62 65 20 69 6d 70 |rator ca|n be imp|
|000003a0| 6c 65 6d 65 6e 74 65 64 | 20 77 69 74 68 20 61 6e |lemented| with an|
|000003b0| 20 61 72 72 61 79 20 72 | 65 66 65 72 65 6e 63 65 | array r|eference|
|000003c0| 2e 0d 49 66 20 49 20 64 | 6f 6e 27 74 20 63 6f 6e |..If I d|on't con|
|000003d0| 76 65 72 74 20 61 20 6e | 6f 64 65 27 73 20 6e 61 |vert a n|ode's na|
|000003e0| 6d 65 2c 20 74 68 65 20 | 6f 6e 6c 79 20 70 65 6e |me, the |only pen|
|000003f0| 61 6c 74 79 20 69 73 20 | 74 68 61 74 20 74 68 65 |alty is |that the|
|00000400| 20 74 72 65 65 0d 6d 69 | 67 68 74 20 62 65 20 62 | tree.mi|ght be b|
|00000410| 69 67 67 65 72 2e 0d 28 | 43 6f 64 65 20 67 65 6e |igger..(|Code gen|
|00000420| 65 72 61 74 69 6f 6e 20 | 77 69 6c 6c 20 62 65 20 |eration |will be |
|00000430| 64 69 66 66 65 72 65 6e | 74 20 66 6f 72 20 74 68 |differen|t for th|
|00000440| 65 20 74 77 6f 20 63 61 | 73 65 73 2e 29 0d 40 0d |e two ca|ses.).@.|
|00000450| 4e 6f 77 2c 20 74 68 65 | 20 64 69 72 74 79 20 72 |Now, the| dirty r|
|00000460| 65 70 72 65 73 65 6e 74 | 61 74 69 6f 6e 20 74 72 |epresent|ation tr|
|00000470| 69 63 6b 3a 20 0d 49 20 | 63 61 6e 20 72 65 70 72 |ick: .I |can repr|
|00000480| 65 73 65 6e 74 20 61 20 | 73 65 74 20 6f 66 20 6e |esent a |set of n|
|00000490| 75 6d 62 65 72 73 20 24 | 53 24 20 28 61 20 75 6e |umbers $|S$ (a un|
|000004a0| 69 6f 6e 20 6f 66 20 69 | 6e 74 65 72 76 61 6c 73 |ion of i|ntervals|
|000004b0| 29 20 61 73 20 74 77 6f | 0d 73 65 74 73 2c 20 24 |) as two|.sets, $|
|000004c0| 6c 6f 24 20 61 6e 64 20 | 24 68 69 24 2c 20 73 75 |lo$ and |$hi$, su|
|000004d0| 63 68 20 74 68 61 74 0d | 5c 62 65 67 69 6e 7b 69 |ch that.|\begin{i|
|000004e0| 74 65 6d 69 7a 65 7d 0d | 25 20 6c 32 68 20 73 75 |temize}.|% l2h su|
|000004f0| 62 73 74 69 74 75 74 69 | 6f 6e 20 63 61 70 20 3c |bstituti|on cap <|
|00000500| 62 3e 69 6e 74 65 72 73 | 65 63 74 3c 2f 62 3e 23 |b>inters|ect</b>#|
|00000510| 0d 25 20 6c 32 68 20 73 | 75 62 73 74 69 74 75 74 |.% l2h s|ubstitut|
|00000520| 69 6f 6e 20 63 75 70 20 | 3c 62 3e 75 6e 69 6f 6e |ion cup |<b>union|
|00000530| 3c 2f 62 3e 23 0d 25 20 | 6c 32 68 20 73 75 62 73 |</b>#.% |l2h subs|
|00000540| 74 69 74 75 74 69 6f 6e | 20 65 6d 70 74 79 73 65 |titution| emptyse|
|00000550| 74 20 3c 62 3e 65 6d 70 | 74 79 23 73 65 74 3c 2f |t <b>emp|ty#set</|
|00000560| 62 3e 0d 5c 69 74 65 6d | 5b 5d 20 24 6c 6f 20 5c |b>.\item|[] $lo \|
|00000570| 63 61 70 20 68 69 20 3d | 20 5c 65 6d 70 74 79 73 |cap hi =| \emptys|
|00000580| 65 74 24 0d 5c 69 74 65 | 6d 5b 5d 20 69 66 20 24 |et$.\ite|m[] if $|
|00000590| 7b 5c 74 74 20 73 6f 72 | 74 7d 28 6c 6f 20 5c 63 |{\tt sor|t}(lo \c|
|000005a0| 75 70 20 68 69 29 20 3d | 20 61 2c 20 62 2c 20 63 |up hi) =| a, b, c|
|000005b0| 2c 20 64 2c 20 5c 6c 64 | 6f 74 73 24 2c 20 74 68 |, d, \ld|ots$, th|
|000005c0| 65 6e 0d 20 20 20 20 20 | 20 24 53 20 3d 20 5b 61 |en.     | $S = [a|
|000005d0| 2c 62 2d 31 5d 20 5c 63 | 75 70 20 5b 63 2c 64 2d |,b-1] \c|up [c,d-|
|000005e0| 31 5d 20 5c 63 75 70 20 | 5c 6c 64 6f 74 73 24 2e |1] \cup |\ldots$.|
|000005f0| 0d 5c 65 6e 64 7b 69 74 | 65 6d 69 7a 65 7d 0d 54 |.\end{it|emize}.T|
|00000600| 68 65 20 70 72 6f 63 65 | 64 75 72 65 20 5b 5b 61 |he proce|dure [[a|
|00000610| 64 64 69 6e 74 65 72 76 | 61 6c 5d 5d 20 61 64 64 |ddinterv|al]] add|
|00000620| 73 20 61 20 6e 65 77 20 | 69 6e 74 65 72 76 61 6c |s a new |interval|
|00000630| 20 74 6f 20 73 75 63 68 | 20 61 20 73 65 74 20 24 | to such| a set $|
|00000640| 53 24 2c 0d 72 65 6c 79 | 69 6e 67 20 6f 6e 20 74 |S$,.rely|ing on t|
|00000650| 68 65 20 66 61 63 74 20 | 74 68 61 74 20 6e 6f 20 |he fact |that no |
|00000660| 74 77 6f 20 69 6e 74 65 | 72 76 61 6c 73 20 6f 76 |two inte|rvals ov|
|00000670| 65 72 6c 61 70 2e 0d 3c | 3c 2a 3e 3e 3d 0d 70 72 |erlap..<|<*>>=.pr|
|00000680| 6f 63 65 64 75 72 65 20 | 61 64 64 69 6e 74 65 72 |ocedure |addinter|
|00000690| 76 61 6c 28 6c 6f 73 65 | 74 2c 20 68 69 73 65 74 |val(lose|t, hiset|
|000006a0| 2c 20 6c 6f 6e 75 6d 2c | 20 68 69 6e 75 6d 29 0d |, lonum,| hinum).|
|000006b0| 20 20 20 20 69 66 20 6d | 65 6d 62 65 72 28 6c 6f |    if m|ember(lo|
|000006c0| 73 65 74 2c 20 68 69 6e | 75 6d 29 20 74 68 65 6e |set, hin|um) then|
|000006d0| 20 64 65 6c 65 74 65 28 | 6c 6f 73 65 74 2c 20 68 | delete(|loset, h|
|000006e0| 69 6e 75 6d 29 20 65 6c | 73 65 20 69 6e 73 65 72 |inum) el|se inser|
|000006f0| 74 28 68 69 73 65 74 2c | 20 68 69 6e 75 6d 29 0d |t(hiset,| hinum).|
|00000700| 20 20 20 20 69 66 20 6d | 65 6d 62 65 72 28 68 69 |    if m|ember(hi|
|00000710| 73 65 74 2c 20 6c 6f 6e | 75 6d 29 20 74 68 65 6e |set, lon|um) then|
|00000720| 20 64 65 6c 65 74 65 28 | 68 69 73 65 74 2c 20 6c | delete(|hiset, l|
|00000730| 6f 6e 75 6d 29 20 65 6c | 73 65 20 69 6e 73 65 72 |onum) el|se inser|
|00000740| 74 28 6c 6f 73 65 74 2c | 20 6c 6f 6e 75 6d 29 0d |t(loset,| lonum).|
|00000750| 20 20 20 20 72 65 74 75 | 72 6e 0d 65 6e 64 0d 40 |    retu|rn.end.@|
|00000760| 0d 54 6f 20 63 6f 6e 76 | 65 72 74 20 74 72 65 65 |.To conv|ert tree|
|00000770| 73 20 74 6f 20 64 61 67 | 73 20 49 20 6e 65 65 64 |s to dag|s I need|
|00000780| 20 74 6f 20 62 65 20 61 | 62 6c 65 20 74 6f 20 63 | to be a|ble to c|
|00000790| 6f 6d 70 61 72 65 20 74 | 77 6f 20 6e 6f 64 65 73 |ompare t|wo nodes|
|000007a0| 0d 66 6f 72 20 73 74 72 | 75 63 74 75 72 61 6c 20 |.for str|uctural |
|000007b0| 69 64 65 6e 74 69 74 79 | 2c 20 61 6e 64 20 74 68 |identity|, and th|
|000007c0| 65 20 65 61 73 69 65 73 | 74 20 77 61 79 20 69 73 |e easies|t way is|
|000007d0| 20 74 6f 20 63 6f 6d 70 | 75 74 65 20 61 20 63 61 | to comp|ute a ca|
|000007e0| 6e 6f 6e 69 63 61 6c 0d | 72 65 70 72 65 73 65 6e |nonical.|represen|
|000007f0| 74 61 74 69 6f 6e 20 61 | 73 20 61 20 73 74 72 69 |tation a|s a stri|
|00000800| 6e 67 3a 5c 70 61 72 5c | 6e 6f 69 6e 64 65 6e 74 |ng:\par\|noindent|
|00000810| 20 5b 5b 0d 20 20 20 6e | 6f 64 65 20 3a 20 5b 66 | [[.   n|ode : [f|
|00000820| 6e 61 6d 65 3a 70 61 74 | 69 6d 61 67 65 28 6c 69 |name:pat|image(li|
|00000830| 73 74 20 6f 66 20 65 64 | 67 65 73 29 5d 0d 20 20 |st of ed|ges)].  |
|00000840| 20 20 20 20 20 20 7c 20 | 3c 4e 4f 4d 41 54 43 48 |      | |<NOMATCH|
|00000850| 3e 0d 20 20 20 20 20 20 | 20 20 7c 20 28 69 6d 61 |>.      |  | (ima|
|00000860| 67 65 28 6e 6f 64 65 2e | 6e 61 6d 65 29 3a 69 6d |ge(node.|name):im|
|00000870| 61 67 65 28 6e 6f 64 65 | 2e 63 73 2e 61 72 6d 73 |age(node|.cs.arms|
|00000880| 5b 31 5d 2e 6f 72 69 67 | 69 6e 61 6c 29 29 0d 20 |[1].orig|inal)). |
|00000890| 20 20 65 64 67 65 20 3a | 20 70 61 74 69 6d 61 67 |  edge :| patimag|
|000008a0| 65 28 6c 69 73 74 20 6f | 66 20 73 6f 72 74 28 6c |e(list o|f sort(l|
|000008b0| 6f 73 65 74 20 2b 2b 20 | 68 69 73 65 74 29 29 3a |oset ++ |hiset)):|
|000008c0| 6e 6f 64 65 0d 5d 5d 0d | 3c 3c 2a 3e 3e 3d 0d 70 |node.]].|<<*>>=.p|
|000008d0| 72 6f 63 65 64 75 72 65 | 20 6e 6f 64 65 74 6f 73 |rocedure| nodetos|
|000008e0| 74 72 69 6e 67 28 6e 2c | 20 64 65 70 74 68 29 0d |tring(n,| depth).|
|000008f0| 20 20 20 20 73 74 61 74 | 69 63 20 63 61 63 68 65 |    stat|ic cache|
|00000900| 20 0d 20 20 20 20 69 6e | 69 74 69 61 6c 20 63 61 | .    in|itial ca|
|00000910| 63 68 65 20 3a 3d 20 74 | 61 62 6c 65 28 29 0d 20 |che := t|able(). |
|00000920| 20 20 20 2f 64 65 70 74 | 68 20 3a 3d 20 30 0d 20 |   /dept|h := 0. |
|00000930| 20 20 20 69 66 20 2f 63 | 61 63 68 65 5b 6e 5d 20 |   if /c|ache[n] |
|00000940| 74 68 65 6e 0d 20 20 20 | 20 20 20 20 20 69 66 20 |then.   |     if |
|00000950| 2a 6e 2e 63 68 69 6c 64 | 72 65 6e 20 3e 20 30 20 |*n.child|ren > 0 |
|00000960| 74 68 65 6e 20 7b 0d 20 | 20 20 20 20 20 20 20 20 |then {. |        |
|00000970| 20 20 20 72 65 73 75 6c | 74 20 3a 3d 20 22 5b 22 |   resul|t := "["|
|00000980| 20 7c 7c 20 6e 2e 66 69 | 65 6c 64 2e 6e 61 6d 65 | || n.fi|eld.name|
|00000990| 20 7c 7c 20 22 3a 22 0d | 09 20 20 20 20 65 76 65 | || ":".|.    eve|
|000009a0| 72 79 20 72 65 73 75 6c | 74 20 7c 7c 3a 3d 20 65 |ry resul|t ||:= e|
|000009b0| 64 67 65 74 6f 73 74 72 | 69 6e 67 28 21 6e 2e 63 |dgetostr|ing(!n.c|
|000009c0| 68 69 6c 64 72 65 6e 2c | 20 64 65 70 74 68 2b 32 |hildren,| depth+2|
|000009d0| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 63 61 |).      |      ca|
|000009e0| 63 68 65 5b 6e 5d 20 3a | 3d 20 72 65 73 75 6c 74 |che[n] :|= result|
|000009f0| 20 7c 7c 20 22 5d 22 0d | 20 20 20 20 20 20 20 20 | || "]".|        |
|00000a00| 7d 20 65 6c 73 65 20 69 | 66 20 2a 6e 2e 63 73 2e |} else i|f *n.cs.|
|00000a10| 61 72 6d 73 20 3d 20 30 | 20 74 68 65 6e 0d 20 20 |arms = 0| then.  |
|00000a20| 20 20 20 20 20 20 20 20 | 20 20 63 61 63 68 65 5b |        |  cache[|
|00000a30| 6e 5d 20 3a 3d 20 22 3c | 4e 4f 4d 41 54 43 48 3e |n] := "<|NOMATCH>|
|00000a40| 22 0d 20 20 20 20 20 20 | 20 20 65 6c 73 65 20 0d |".      |  else .|
|00000a50| 20 20 20 20 20 20 20 20 | 20 20 20 20 63 61 63 68 |        |    cach|
|00000a60| 65 5b 6e 5d 20 3a 3d 20 | 22 28 22 20 7c 7c 20 69 |e[n] := |"(" || i|
|00000a70| 6d 61 67 65 28 6e 2e 6e | 61 6d 65 29 20 7c 7c 20 |mage(n.n|ame) || |
|00000a80| 22 3a 22 20 7c 7c 20 69 | 6d 61 67 65 28 6e 2e 63 |":" || i|mage(n.c|
|00000a90| 73 2e 61 72 6d 73 5b 31 | 5d 2e 6f 72 69 67 69 6e |s.arms[1|].origin|
|00000aa0| 61 6c 29 20 7c 7c 22 29 | 22 0d 20 20 20 20 72 65 |al) ||")|".    re|
|00000ab0| 74 75 72 6e 20 5c 63 61 | 63 68 65 5b 6e 5d 0d 65 |turn \ca|che[n].e|
|00000ac0| 6e 64 0d 0d 70 72 6f 63 | 65 64 75 72 65 20 65 64 |nd..proc|edure ed|
|00000ad0| 67 65 74 6f 73 74 72 69 | 6e 67 28 65 2c 64 65 70 |getostri|ng(e,dep|
|00000ae0| 74 68 29 0d 20 20 20 20 | 72 65 74 75 72 6e 20 6c |th).    |return l|
|00000af0| 65 66 74 28 22 5c 6e 22 | 2c 20 64 65 70 74 68 29 |eft("\n"|, depth)|
|00000b00| 20 7c 7c 20 0d 20 20 20 | 20 20 20 20 20 20 20 22 | || .   |       "|
|00000b10| 7b 22 20 7c 7c 20 70 61 | 74 69 6d 61 67 65 28 73 |{" || pa|timage(s|
|00000b20| 6f 72 74 28 65 2e 6c 6f | 20 2b 2b 20 65 2e 68 69 |ort(e.lo| ++ e.hi|
|00000b30| 29 29 20 7c 7c 20 22 3a | 22 20 7c 7c 20 6e 6f 64 |)) || ":|" || nod|
|00000b40| 65 74 6f 73 74 72 69 6e | 67 28 65 2e 6e 6f 64 65 |etostrin|g(e.node|
|00000b50| 2c 64 65 70 74 68 29 20 | 7c 7c 20 22 7d 22 0d 65 |,depth) ||| "}".e|
|00000b60| 6e 64 0d 40 0d 43 6f 6e | 76 65 72 73 69 6f 6e 20 |nd.@.Con|version |
|00000b70| 74 6f 20 64 61 67 20 69 | 73 20 74 68 65 20 75 73 |to dag i|s the us|
|00000b80| 75 61 6c 20 62 6f 74 74 | 6f 6d 2d 75 70 20 68 61 |ual bott|om-up ha|
|00000b90| 73 68 69 6e 67 3b 20 68 | 65 72 65 20 49 20 63 6f |shing; h|ere I co|
|00000ba0| 6d 70 75 74 65 20 74 68 | 65 0d 73 74 72 69 6e 67 |mpute th|e.string|
|00000bb0| 20 61 6e 64 20 74 68 65 | 6e 20 75 73 65 20 74 68 | and the|n use th|
|00000bc0| 65 20 73 74 72 69 6e 67 | 20 74 6f 20 69 6e 64 65 |e string| to inde|
|00000bd0| 78 20 69 6e 74 6f 20 61 | 20 74 61 62 6c 65 2e 0d |x into a| table..|
|00000be0| 54 68 65 20 72 65 61 6c | 20 77 6f 72 6b 20 6f 66 |The real| work of|
|00000bf0| 20 6d 65 72 67 69 6e 67 | 20 65 64 67 65 73 20 69 | merging| edges i|
|00000c00| 73 20 64 6f 6e 65 20 62 | 79 20 5b 5b 63 6f 6d 62 |s done b|y [[comb|
|00000c10| 69 6e 65 63 68 69 6c 64 | 72 65 6e 5d 5d 2e 0d 49 |inechild|ren]]..I|
|00000c20| 66 20 65 64 67 65 20 6d | 65 72 67 69 6e 67 20 72 |f edge m|erging r|
|00000c30| 65 73 75 6c 74 73 20 69 | 6e 20 61 20 73 69 6e 67 |esults i|n a sing|
|00000c40| 6c 65 20 65 61 63 68 2c | 20 74 68 65 20 6e 6f 64 |le each,| the nod|
|00000c50| 65 20 69 73 20 72 65 70 | 6c 61 63 65 64 20 62 79 |e is rep|laced by|
|00000c60| 0d 69 74 73 20 63 68 69 | 6c 64 2c 20 70 72 6f 76 |.its chi|ld, prov|
|00000c70| 69 64 65 64 20 74 68 65 | 20 65 64 67 65 20 72 65 |ided the| edge re|
|00000c80| 61 6c 6c 79 20 63 6f 76 | 65 72 73 20 61 6c 6c 20 |ally cov|ers all |
|00000c90| 70 6f 73 73 69 62 6c 65 | 20 76 61 6c 75 65 73 0d |possible| values.|
|00000ca0| 6f 66 20 74 68 65 20 66 | 69 65 6c 64 2e 0d 3c 3c |of the f|ield..<<|
|00000cb0| 2a 3e 3e 3d 0d 70 72 6f | 63 65 64 75 72 65 20 74 |*>>=.pro|cedure t|
|00000cc0| 72 65 65 32 64 61 67 28 | 6e 2c 20 6e 6f 64 65 74 |ree2dag(|n, nodet|
|00000cd0| 61 62 6c 65 2c 20 64 65 | 70 74 68 29 0d 20 20 20 |able, de|pth).   |
|00000ce0| 20 2f 6e 6f 64 65 74 61 | 62 6c 65 20 3a 3d 20 74 | /nodeta|ble := t|
|00000cf0| 61 62 6c 65 28 29 0d 20 | 20 20 20 2f 64 65 70 74 |able(). |   /dept|
|00000d00| 68 20 3a 3d 20 30 0d 20 | 20 20 20 69 66 20 2a 6e |h := 0. |   if *n|
|00000d10| 2e 63 68 69 6c 64 72 65 | 6e 20 3e 20 30 20 74 68 |.childre|n > 0 th|
|00000d20| 65 6e 0d 20 20 20 20 20 | 20 20 20 63 6f 6d 62 69 |en.     |   combi|
|00000d30| 6e 65 63 68 69 6c 64 72 | 65 6e 28 6e 2c 20 6e 6f |nechildr|en(n, no|
|00000d40| 64 65 74 61 62 6c 65 2c | 20 64 65 70 74 68 2b 32 |detable,| depth+2|
|00000d50| 29 09 23 20 63 6f 6e 76 | 65 72 74 73 20 65 64 67 |).# conv|erts edg|
|00000d60| 65 73 20 74 6f 20 73 65 | 74 20 66 6f 72 6d 0d 20 |es to se|t form. |
|00000d70| 20 20 20 69 66 20 2a 6e | 2e 63 68 69 6c 64 72 65 |   if *n|.childre|
|00000d80| 6e 20 3d 20 31 20 74 68 | 65 6e 20 7b 0d 20 20 20 |n = 1 th|en {.   |
|00000d90| 20 20 20 20 20 65 20 3a | 3d 20 6e 2e 63 68 69 6c |     e :|= n.chil|
|00000da0| 64 72 65 6e 5b 31 5d 0d | 20 20 20 20 20 20 20 20 |dren[1].|        |
|00000db0| 69 66 20 63 6f 76 65 72 | 73 28 6e 2e 63 68 69 6c |if cover|s(n.chil|
|00000dc0| 64 72 65 6e 5b 31 5d 2c | 20 6e 2e 66 69 65 6c 64 |dren[1],| n.field|
|00000dd0| 2e 68 69 20 2d 20 6e 2e | 66 69 65 6c 64 2e 6c 6f |.hi - n.|field.lo|
|00000de0| 29 20 74 68 65 6e 0d 20 | 20 20 20 20 20 20 20 20 |) then. |        |
|00000df0| 20 20 20 6e 20 3a 3d 20 | 6e 2e 63 68 69 6c 64 72 |   n := |n.childr|
|00000e00| 65 6e 5b 31 5d 2e 6e 6f | 64 65 20 20 20 20 20 23 |en[1].no|de     #|
|00000e10| 20 61 6c 6c 20 72 6f 61 | 64 73 20 74 6f 20 63 68 | all roa|ds to ch|
|00000e20| 69 6c 64 3a 20 68 6f 69 | 73 74 20 69 74 0d 20 20 |ild: hoi|st it.  |
|00000e30| 20 20 20 20 20 20 65 6c | 73 65 0d 20 20 20 20 20 |      el|se.     |
|00000e40| 20 20 20 20 20 20 20 77 | 61 72 6e 69 6e 67 28 22 |       w|arning("|
|00000e50| 6e 6f 64 65 20 77 69 74 | 68 20 6f 6e 65 20 63 68 |node wit|h one ch|
|00000e60| 69 6c 64 20 64 6f 65 73 | 6e 27 74 20 6d 61 74 63 |ild does|n't matc|
|00000e70| 68 20 61 6c 6c 20 63 61 | 73 65 73 22 29 20 20 20 |h all ca|ses")   |
|00000e80| 20 0d 20 20 20 20 7d 0d | 20 20 20 20 73 20 3a 3d | .    }.|    s :=|
|00000e90| 20 6e 6f 64 65 74 6f 73 | 74 72 69 6e 67 28 6e 2c | nodetos|tring(n,|
|00000ea0| 20 64 65 70 74 68 29 0d | 20 20 20 20 2f 6e 6f 64 | depth).|    /nod|
|00000eb0| 65 74 61 62 6c 65 5b 73 | 5d 20 3a 3d 20 6e 0d 20 |etable[s|] := n. |
|00000ec0| 20 20 20 72 65 74 75 72 | 6e 20 6e 6f 64 65 74 61 |   retur|n nodeta|
|00000ed0| 62 6c 65 5b 73 5d 0d 65 | 6e 64 0d 40 0d 48 65 72 |ble[s].e|nd.@.Her|
|00000ee0| 65 27 73 20 77 68 65 72 | 65 20 49 20 63 68 65 63 |e's wher|e I chec|
|00000ef0| 6b 20 63 6f 76 65 72 61 | 67 65 2e 0d 4f 6e 6c 79 |k covera|ge..Only|
|00000f00| 20 73 75 63 63 65 73 73 | 20 6f 72 20 66 61 69 6c | success| or fail|
|00000f10| 75 72 65 20 6f 66 20 5b | 5b 63 6f 76 65 72 73 5d |ure of [|[covers]|
|00000f20| 5d 20 69 73 20 6d 65 61 | 6e 69 6e 67 66 75 6c 2c |] is mea|ningful,|
|00000f30| 20 6e 6f 74 0d 74 68 65 | 20 76 61 6c 75 65 20 72 | not.the| value r|
|00000f40| 65 74 75 72 6e 65 64 2e | 0d 3c 3c 2a 3e 3e 3d 0d |eturned.|.<<*>>=.|
|00000f50| 70 72 6f 63 65 64 75 72 | 65 20 63 6f 76 65 72 73 |procedur|e covers|
|00000f60| 28 65 2c 20 77 69 64 74 | 68 29 0d 20 20 20 20 6c |(e, widt|h).    l|
|00000f70| 20 3a 3d 20 73 6f 72 74 | 28 65 2e 6c 6f 20 2b 2b | := sort|(e.lo ++|
|00000f80| 20 65 2e 68 69 29 0d 20 | 20 20 20 72 65 74 75 72 | e.hi). |   retur|
|00000f90| 6e 20 2a 6c 20 3d 20 32 | 20 26 20 6c 5b 31 5d 20 |n *l = 2| & l[1] |
|00000fa0| 3d 20 30 20 26 20 6c 5b | 32 5d 20 3d 20 32 5e 77 |= 0 & l[|2] = 2^w|
|00000fb0| 69 64 74 68 0d 65 6e 64 | 0d 40 0d 54 68 65 20 63 |idth.end|.@.The c|
|00000fc0| 6f 6d 70 6c 69 63 61 74 | 65 64 20 73 74 75 66 66 |omplicat|ed stuff|
|00000fd0| 20 68 65 72 65 20 69 73 | 20 69 64 65 6e 74 69 66 | here is| identif|
|00000fe0| 79 69 6e 67 20 61 20 6e | 61 6d 65 20 61 72 72 61 |ying a n|ame arra|
|00000ff0| 79 2e 0d 41 74 20 65 61 | 63 68 20 6e 6f 64 65 2c |y..At ea|ch node,|
|00001000| 20 65 69 74 68 65 72 20 | 61 6c 6c 20 65 64 67 65 | either |all edge|
|00001010| 73 20 67 6f 20 69 6e 20 | 61 6e 20 65 78 69 74 69 |s go in |an exiti|
|00001020| 6e 67 20 6e 61 6d 65 20 | 61 72 72 61 79 20 0d 6f |ng name |array .o|
|00001030| 72 20 61 20 6e 65 77 20 | 6e 61 6d 65 20 61 72 72 |r a new |name arr|
|00001040| 61 79 20 69 73 20 75 73 | 65 64 2e 0d 49 66 20 6e |ay is us|ed..If n|
|00001050| 6f 74 2c 20 49 20 63 72 | 65 61 74 65 20 61 20 6e |ot, I cr|eate a n|
|00001060| 65 77 20 6f 6e 65 2e 0d | 3c 3c 2a 3e 3e 3d 0d 72 |ew one..|<<*>>=.r|
|00001070| 65 63 6f 72 64 20 6e 61 | 6d 65 61 72 72 61 79 28 |ecord na|mearray(|
|00001080| 66 69 65 6c 64 2c 20 74 | 62 6c 2c 20 68 69 2c 20 |field, t|bl, hi, |
|00001090| 63 6f 64 65 6e 61 6d 65 | 29 0d 09 23 20 66 69 65 |codename|)..# fie|
|000010a0| 6c 64 20 75 73 65 64 20 | 61 73 20 69 6e 64 65 78 |ld used |as index|
|000010b0| 2c 20 74 61 62 6c 65 5b | 69 6e 74 65 67 65 72 5d |, table[|integer]|
|000010c0| 20 6f 66 20 6e 61 6d 65 | 2c 20 62 6f 75 6e 64 20 | of name|, bound |
|000010d0| 6f 6e 20 74 61 62 6c 65 | 2c 20 6e 61 6d 65 20 6f |on table|, name o|
|000010e0| 66 20 74 68 69 73 20 61 | 72 72 61 79 0d 67 6c 6f |f this a|rray.glo|
|000010f0| 62 61 6c 20 6e 61 74 61 | 62 6c 65 0d 3c 3c 2a 3e |bal nata|ble.<<*>|
|00001100| 3e 3d 0d 70 72 6f 63 65 | 64 75 72 65 20 61 72 72 |>=.proce|dure arr|
|00001110| 61 79 63 61 6e 64 69 64 | 61 74 65 73 28 6e 29 0d |aycandid|ates(n).|
|00001120| 20 20 20 20 69 6e 69 74 | 69 61 6c 20 4d 41 58 52 |    init|ial MAXR|
|00001130| 41 4e 47 45 20 3a 3d 20 | 33 32 0d 20 20 20 20 73 |ANGE := |32.    s|
|00001140| 75 73 70 65 6e 64 20 65 | 20 3a 3d 20 21 6e 2e 63 |uspend e| := !n.c|
|00001150| 68 69 6c 64 72 65 6e 20 | 26 20 74 79 70 65 28 65 |hildren |& type(e|
|00001160| 2e 6e 6f 64 65 2e 6e 61 | 6d 65 29 20 3d 3d 20 22 |.node.na|me) == "|
|00001170| 73 74 72 69 6e 67 22 20 | 26 20 0d 20 20 20 20 20 |string" |& .     |
|00001180| 20 20 20 20 20 20 20 65 | 2e 68 69 20 2d 20 65 2e |       e|.hi - e.|
|00001190| 6c 6f 20 3c 3d 20 4d 41 | 58 52 41 4e 47 45 20 26 |lo <= MA|XRANGE &|
|000011a0| 20 65 0d 65 6e 64 0d 0d | 70 72 6f 63 65 64 75 72 | e.end..|procedur|
|000011b0| 65 20 63 6f 6d 62 69 6e | 65 63 68 69 6c 64 72 65 |e combin|echildre|
|000011c0| 6e 28 6e 2c 20 6e 6f 64 | 65 74 61 62 6c 65 2c 20 |n(n, nod|etable, |
|000011d0| 64 65 70 74 68 29 0d 20 | 20 20 20 69 6e 69 74 69 |depth). |   initi|
|000011e0| 61 6c 20 6e 61 74 61 62 | 6c 65 20 3a 3d 20 74 61 |al natab|le := ta|
|000011f0| 62 6c 65 28 29 0d 0d 20 | 20 20 20 69 66 20 61 72 |ble().. |   if ar|
|00001200| 72 61 79 63 61 6e 64 69 | 64 61 74 65 73 28 6e 29 |raycandi|dates(n)|
|00001210| 2e 6e 6f 64 65 2e 6e 61 | 6d 65 20 7e 3d 3d 20 61 |.node.na|me ~== a|
|00001220| 72 72 61 79 63 61 6e 64 | 69 64 61 74 65 73 28 6e |rraycand|idates(n|
|00001230| 29 2e 6e 6f 64 65 2e 6e | 61 6d 65 20 74 68 65 6e |).node.n|ame then|
|00001240| 20 7b 0d 20 20 20 20 20 | 20 20 20 3c 3c 63 68 61 | {.     |   <<cha|
|00001250| 6e 67 65 20 6e 61 6d 65 | 73 20 6f 66 20 63 68 69 |nge name|s of chi|
|00001260| 6c 64 72 65 6e 20 66 72 | 6f 6d 20 73 74 72 69 6e |ldren fr|om strin|
|00001270| 67 73 20 74 6f 20 6e 61 | 6d 65 61 72 72 61 79 73 |gs to na|mearrays|
|00001280| 20 77 68 65 6e 20 70 6f | 73 73 69 62 6c 65 3e 3e | when po|ssible>>|
|00001290| 0d 20 20 20 20 7d 0d 0d | 20 20 20 20 6c 6f 74 61 |.    }..|    lota|
|000012a0| 62 6c 65 20 3a 3d 20 74 | 61 62 6c 65 28 29 0d 20 |ble := t|able(). |
|000012b0| 20 20 20 68 69 74 61 62 | 6c 65 20 3a 3d 20 74 61 |   hitab|le := ta|
|000012c0| 62 6c 65 28 29 0d 20 20 | 20 20 65 76 65 72 79 20 |ble().  |  every |
|000012d0| 65 20 3a 3d 20 21 6e 2e | 63 68 69 6c 64 72 65 6e |e := !n.|children|
|000012e0| 20 26 20 63 68 69 6c 64 | 20 3a 3d 20 74 72 65 65 | & child| := tree|
|000012f0| 32 64 61 67 28 65 2e 6e | 6f 64 65 2c 20 6e 6f 64 |2dag(e.n|ode, nod|
|00001300| 65 74 61 62 6c 65 2c 20 | 64 65 70 74 68 29 20 64 |etable, |depth) d|
|00001310| 6f 20 7b 0d 20 20 20 20 | 20 20 20 20 2f 6c 6f 74 |o {.    |    /lot|
|00001320| 61 62 6c 65 5b 63 68 69 | 6c 64 5d 20 3a 3d 20 73 |able[chi|ld] := s|
|00001330| 65 74 28 29 0d 20 20 20 | 20 20 20 20 20 2f 68 69 |et().   |     /hi|
|00001340| 74 61 62 6c 65 5b 63 68 | 69 6c 64 5d 20 3a 3d 20 |table[ch|ild] := |
|00001350| 73 65 74 28 29 0d 20 20 | 20 20 20 20 20 20 61 64 |set().  |      ad|
|00001360| 64 69 6e 74 65 72 76 61 | 6c 28 6c 6f 74 61 62 6c |dinterva|l(lotabl|
|00001370| 65 5b 63 68 69 6c 64 5d | 2c 20 68 69 74 61 62 6c |e[child]|, hitabl|
|00001380| 65 5b 63 68 69 6c 64 5d | 2c 20 65 2e 6c 6f 2c 20 |e[child]|, e.lo, |
|00001390| 65 2e 68 69 29 0d 20 20 | 20 20 7d 0d 20 20 20 20 |e.hi).  |  }.    |
|000013a0| 6e 2e 63 68 69 6c 64 72 | 65 6e 20 3a 3d 20 5b 5d |n.childr|en := []|
|000013b0| 0d 20 20 20 20 65 76 65 | 72 79 20 63 68 69 6c 64 |.    eve|ry child|
|000013c0| 20 3a 3d 20 6b 65 79 28 | 6c 6f 74 61 62 6c 65 29 | := key(|lotable)|
|000013d0| 20 64 6f 0d 20 20 20 20 | 20 20 20 20 70 75 74 28 | do.    |    put(|
|000013e0| 6e 2e 63 68 69 6c 64 72 | 65 6e 2c 20 65 64 67 65 |n.childr|en, edge|
|000013f0| 28 63 68 69 6c 64 2c 20 | 6c 6f 74 61 62 6c 65 5b |(child, |lotable[|
|00001400| 63 68 69 6c 64 5d 2c 20 | 68 69 74 61 62 6c 65 5b |child], |hitable[|
|00001410| 63 68 69 6c 64 5d 29 29 | 0d 20 20 20 20 72 65 74 |child]))|.    ret|
|00001420| 75 72 6e 0d 65 6e 64 0d | 3c 3c 63 68 61 6e 67 65 |urn.end.|<<change|
|00001430| 20 6e 61 6d 65 73 20 6f | 66 20 63 68 69 6c 64 72 | names o|f childr|
|00001440| 65 6e 20 66 72 6f 6d 20 | 73 74 72 69 6e 67 73 20 |en from |strings |
|00001450| 74 6f 20 6e 61 6d 65 61 | 72 72 61 79 73 20 77 68 |to namea|rrays wh|
|00001460| 65 6e 20 70 6f 73 73 69 | 62 6c 65 3e 3e 3d 0d 6d |en possi|ble>>=.m|
|00001470| 69 67 68 74 75 73 65 20 | 3a 3d 20 73 65 74 28 29 |ightuse |:= set()|
|00001480| 20 20 20 20 20 20 20 20 | 20 20 20 23 20 6e 61 6d |        |   # nam|
|00001490| 65 20 61 72 72 61 79 73 | 20 77 65 20 6d 69 67 68 |e arrays| we migh|
|000014a0| 74 20 75 73 65 20 6d 75 | 73 74 20 68 61 76 65 20 |t use mu|st have |
|000014b0| 72 69 67 68 74 20 66 69 | 65 6c 64 0d 65 76 65 72 |right fi|eld.ever|
|000014c0| 79 20 6e 61 20 3a 3d 20 | 21 5c 6e 61 74 61 62 6c |y na := |!\natabl|
|000014d0| 65 5b 6e 2e 66 69 65 6c | 64 5d 20 64 6f 0d 20 20 |e[n.fiel|d] do.  |
|000014e0| 20 20 69 6e 73 65 72 74 | 28 6d 69 67 68 74 75 73 |  insert|(mightus|
|000014f0| 65 2c 20 6e 61 29 0d 65 | 76 65 72 79 20 65 20 3a |e, na).e|very e :|
|00001500| 3d 20 61 72 72 61 79 63 | 61 6e 64 69 64 61 74 65 |= arrayc|andidate|
|00001510| 73 28 6e 29 20 26 20 6e | 61 20 3a 3d 20 21 6d 69 |s(n) & n|a := !mi|
|00001520| 67 68 74 75 73 65 20 64 | 6f 0d 20 20 20 20 69 66 |ghtuse d|o.    if|
|00001530| 20 5c 6e 61 2e 74 62 6c | 5b 65 2e 6c 6f 20 74 6f | \na.tbl|[e.lo to|
|00001540| 20 65 2e 68 69 20 2d 20 | 31 5d 20 7e 3d 3d 20 65 | e.hi - |1] ~== e|
|00001550| 2e 6e 6f 64 65 2e 6e 61 | 6d 65 20 74 68 65 6e 20 |.node.na|me then |
|00001560| 20 23 20 73 6c 6f 74 20 | 75 73 65 64 20 77 69 74 | # slot |used wit|
|00001570| 68 20 77 72 6f 6e 67 20 | 6e 61 6d 65 0d 20 20 20 |h wrong |name.   |
|00001580| 20 20 20 20 20 64 65 6c | 65 74 65 28 6d 69 67 68 |     del|ete(migh|
|00001590| 74 75 73 65 2c 20 6e 61 | 29 0d 69 66 20 2a 6d 69 |tuse, na|).if *mi|
|000015a0| 67 68 74 75 73 65 20 3e | 20 30 20 74 68 65 6e 0d |ghtuse >| 0 then.|
|000015b0| 20 20 20 20 77 69 6c 6c | 75 73 65 20 3a 3d 20 3f |    will|use := ?|
|000015c0| 6d 69 67 68 74 75 73 65 | 0d 65 6c 73 65 20 7b 0d |mightuse|.else {.|
|000015d0| 20 20 20 20 2f 6e 61 74 | 61 62 6c 65 5b 6e 2e 66 |    /nat|able[n.f|
|000015e0| 69 65 6c 64 5d 20 3a 3d | 20 73 65 74 28 29 0d 20 |ield] :=| set(). |
|000015f0| 20 20 20 69 6e 73 65 72 | 74 28 6e 61 74 61 62 6c |   inser|t(natabl|
|00001600| 65 5b 6e 2e 66 69 65 6c | 64 5d 2c 20 77 69 6c 6c |e[n.fiel|d], will|
|00001610| 75 73 65 20 3a 3d 20 6e | 61 6d 65 61 72 72 61 79 |use := n|amearray|
|00001620| 28 6e 2e 66 69 65 6c 64 | 2c 20 74 61 62 6c 65 28 |(n.field|, table(|
|00001630| 29 2c 20 30 29 29 0d 7d | 0d 65 76 65 72 79 20 65 |), 0)).}|.every e|
|00001640| 20 3a 3d 20 61 72 72 61 | 79 63 61 6e 64 69 64 61 | := arra|ycandida|
|00001650| 74 65 73 28 6e 29 20 26 | 0d 20 20 20 20 20 20 65 |tes(n) &|.      e|
|00001660| 2e 6c 6f 20 2d 20 77 69 | 6c 6c 75 73 65 2e 68 69 |.lo - wi|lluse.hi|
|00001670| 20 3c 3d 20 4d 41 58 52 | 41 4e 47 45 20 64 6f 20 | <= MAXR|ANGE do |
|00001680| 7b 0d 20 20 20 20 20 20 | 20 20 20 20 65 76 65 72 |{.      |    ever|
|00001690| 79 20 77 69 6c 6c 75 73 | 65 2e 74 62 6c 5b 65 2e |y willus|e.tbl[e.|
|000016a0| 6c 6f 20 74 6f 20 65 2e | 68 69 20 2d 20 31 5d 20 |lo to e.|hi - 1] |
|000016b0| 3a 3d 20 65 2e 6e 6f 64 | 65 2e 6e 61 6d 65 3b 0d |:= e.nod|e.name;.|
|000016c0| 20 20 20 20 20 20 20 20 | 20 20 65 2e 6e 6f 64 65 |        |  e.node|
|000016d0| 2e 6e 61 6d 65 20 3a 3d | 20 77 69 6c 6c 75 73 65 |.name :=| willuse|
|000016e0| 0d 20 20 20 20 20 20 20 | 20 20 20 77 69 6c 6c 75 |.       |   willu|
|000016f0| 73 65 2e 68 69 20 3c 3a | 3d 20 65 2e 68 69 0d 20 |se.hi <:|= e.hi. |
|00001700| 20 20 20 20 20 7d 0d 3c | 3c 2a 3e 3e 3d 0d 70 72 |     }.<|<*>>=.pr|
|00001710| 6f 63 65 64 75 72 65 20 | 6e 61 6d 65 73 75 73 65 |ocedure |namesuse|
|00001720| 64 28 6e 2c 20 72 65 73 | 75 6c 74 29 0d 20 20 20 |d(n, res|ult).   |
|00001730| 20 2f 72 65 73 75 6c 74 | 20 3a 3d 20 73 65 74 28 | /result| := set(|
|00001740| 29 0d 20 20 20 20 69 66 | 20 74 79 70 65 28 6e 2e |).    if| type(n.|
|00001750| 6e 61 6d 65 29 20 3d 3d | 20 22 6e 61 6d 65 61 72 |name) ==| "namear|
|00001760| 72 61 79 22 20 74 68 65 | 6e 20 69 6e 73 65 72 74 |ray" the|n insert|
|00001770| 28 72 65 73 75 6c 74 2c | 20 6e 2e 6e 61 6d 65 29 |(result,| n.name)|
|00001780| 0d 20 20 20 20 65 76 65 | 72 79 20 6e 61 6d 65 73 |.    eve|ry names|
|00001790| 75 73 65 64 28 28 21 6e | 2e 63 68 69 6c 64 72 65 |used((!n|.childre|
|000017a0| 6e 29 2e 6e 6f 64 65 2c | 20 72 65 73 75 6c 74 29 |n).node,| result)|
|000017b0| 0d 20 20 20 20 72 65 74 | 75 72 6e 20 72 65 73 75 |.    ret|urn resu|
|000017c0| 6c 74 0d 65 6e 64 0d    |                         |lt.end. |        |
+--------+-------------------------+-------------------------+--------+--------+